Decentralized Online Learning Algorithms for Opportunistic Spectrum Access

摘要

The fundamental problem of multiple secondary users contending foropportunistic spectrum access over multiple channels in cognitive radionetworks has been formulated recently as a decentralized multi-armed bandit(D-MAB) problem. In a D-MAB problem there are $M$ users and $N$ arms (channels)that each offer i.i.d. stochastic rewards with unknown means so long as theyare accessed without collision. The goal is to design a decentralized onlinelearning policy that incurs minimal regret, defined as the difference betweenthe total expected rewards accumulated by a model-aware genie, and thatobtained by all users applying the policy. We make two contributions in thispaper. First, we consider the setting where the users have a prioritizedranking, such that it is desired for the $K$-th-ranked user to learn to accessthe arm offering the $K$-th highest mean reward. For this problem, we presentthe first distributed policy that yields regret that is uniformly logarithmicover time without requiring any prior assumption about the mean rewards.Second, we consider the case when a fair access policy is required, i.e., it isdesired for all users to experience the same mean reward. For this problem, wepresent a distributed policy that yields order-optimal regret scaling withrespect to the number of users and arms, better than previously proposedpolicies in the literature. Both of our distributed policies make use of aninnovative modification of the well known UCB1 policy for the classicmulti-armed bandit problem that allows a single user to learn how to play thearm that yields the $K$-th largest mean reward.